#include<iostream>
#include<cstring>
using namespace std;
int count2011(int x){
	int res=1;
	for(int i=0;i<x;i++){
		res=res*2011%10000;
	}
	return res;
}
//每隔500循环一次
int main(){
	int k;
	cin>>k;
	char num[205];
	int len;
	while(k--){
		cin>>num;
		len=strlen(num);
		int temp=0;
		temp+=num[len-1]-'0';
		if(len>=2) temp+=(num[len-2]-'0')*10;
		if(len>=3) temp+=(num[len-3]-'0')*100;
		temp%=500;
		cout<<count2011(temp)<<endl;
	}
}